机器学习:优化算法(四)—— 遗传算法 发表于 2018-10-23 | 更新于: 2021-06-02 | 分类于 机器学习 | 阅读次数: 字数统计: 1k | 阅读时长 ≈ 4 算法背景术语界定 算法核心问题定义 编码DNA 定义适应度函数 问题求解算法描述经过N代进化,从末代种群中选出最优个体,每轮迭代: 自然选择 交叉重组 基因突变 算法流程图算法实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134#!/usr/bin/env python# coding:utf-8"""遗传算法:“在程序里生宝宝, 杀死不乖的宝宝, 让乖宝宝继续生宝宝”问题描述:1. DNA:将每个可行解编码为DNA2. 适应度函数:get_fitness(NDA)->value,计算每个DNA的适应度进化过程:1. 自然选择(selection):适应性高的个体更容易存活2. 交叉重组(crossover):父代基因片段交换产生新的子代3. 基因突变(mutation):子代有一定概率发生基因突变参数选择:1. 种群大小2. 交叉概率3. 变异概率4. 迭代次数"""import numpy as npfrom erate import get_expected_rateclass Ga(object): def __init__(self, prob_matrix, for_accept, pop_size=50, cross_rate=0.6, mutate_rate=0.02, max_gen=100): """ 初始化遗传算法的进化参数,并生成初代DNA种群 :param prob_matrix: 概率矩阵,type = ndarray,shape = (members_num * captains_num) :param for_accept: 每个队长待接收的队员数,ndarray shape = captains_num :param pop_size: 种群大小 :param cross_rate: 交叉概率 :param mutate_rate: 变异概率 :param max_gen: 最大迭代次数 """ self.L = prob_matrix self.FOR_ACCEPT_NUM = for_accept self.MEMBERS_NUM = self.L.shape[0] self.CAPTAINS_NUM = self.L.shape[1] self.POP_SIZE = pop_size self.DNA_SIZE = L.size self.CROSS_RATE = cross_rate self.MUTATE_RATE = mutate_rate self.MAX_GEN = max_gen self.population = np.random.randint(2, size=(self.POP_SIZE, self.DNA_SIZE)) self.fitness = np.apply_along_axis(self.get_fitness, axis=1, arr=self.population) def get_fitness(self, dna): """ 适应度:计算单个DNA的适应度 :param dna: ndarray :return: 推荐矩阵ndarray """ fitness = get_expected_rate(self.L, self.dna_decode(dna), self.FOR_ACCEPT_NUM) return fitness def dna_encode(self, individual): """ DNA编码:将原始形式的参数编码为二进制形式的NDA列表 :param individual: 存储二进制DNA的矩阵,(pop_size,DNA_size) :return: dna """ dna = individual.ravel('C') return dna def dna_decode(self, dna): """ DNA解码:将二进制形式的DNA解码为原始形式的参数形式 :param dna: 个体dna :return: 原始推荐矩阵 """ individual = dna.reshape(self.MEMBERS_NUM, -1) return individual def select(self, population, fitness): """ 自然选择:依适应度高低/概率从原始种群中有放回地抽样出等容量的新种群,原地修改 :param population: 种群矩阵ndarray :param fitness: 种群中每个个体的适应度,ndarray :return: 新的种群ndarray """ idx = np.random.choice(np.arange(self.POP_SIZE), size=self.POP_SIZE, replace=True, p=fitness / fitness.sum()) population[:] = population[idx] return def crossover(self, population, cross_rate): """ 交叉重组:给定父代群体,通过奇偶个体以一定概率进行交叉重组产生子代群体 :param population: 给定父代群体,通过交叉重组产生子代群体 :param cross_rate: 交叉重组的概率 :return: 子代群体 """ for parent1, parent2 in zip(population[::2],population[1::2]): if np.random.rand() < cross_rate: cross_points = np.random.randint(0, 2, self.DNA_SIZE).astype(np.bool) parent1[cross_points], parent2[cross_points] = parent2[cross_points], parent1[cross_points] return def mutate(self, population, mutation_rate): """ 基因突变:子代DNA中的基因码位有一定概率发生变异 :param population: 待变异的DNA :param mutation_rate: 突变的概率 :return: 变异后的DNA """ mutate_points = np.random.choice(2, size=population.shape, p=[1-mutation_rate, mutation_rate]).astype(np.bool) population[mutate_points] = 1 ^ population[mutate_points] self.fitness = np.apply_along_axis(self.get_fitness, axis=1, arr=self.population) return def evolution(self): """ 种群进化过程,迭代"自然选择-交叉重组-基因突变",退出条件为满足一定的迭代次数 :return: 最优的个体 """ for gen in range(self.MAX_GEN): print('generation: {},fitness: {}'.format(gen, self.fitness.max())) self.select(self.population, self.fitness) self.crossover(self.population, self.CROSS_RATE) self.mutate(self.population, self.MUTATE_RATE) print('generation: {},fitness: {}'.format(gen + 1, self.fitness.max())) res_id = self.fitness.argmax() print('近似最优期望组队成功率:{}'.format(self.fitness[res_id])) print('最优的分配方式: \n{}'.format(self.dna_decode(self.population[res_id]))) return self.fitness[res_id]if __name__ == "__main__": # 测试 L = np.random.rand(6, 3) for_accept = np.ones(shape=L.shape[1], dtype=int) * (L.shape[0]//2) ga = Ga(L, for_accept) ga.evolution() 算法应用优化方法 其他话题 坚持原创技术分享,您的支持将鼓励我继续创作! 打赏 微信支付